package 剑指offer;

/**
 * @Description:
 * @Author: Administrator
 * @Date: 2020-05-02
 */
public class 二叉搜索树的后序遍历 {
    public static boolean VerifySquenceOfBST(int[] sequence) {
        if (sequence == null || sequence.length == 0) {
            return false;
        }
        return verify(sequence, 0, sequence.length - 1, Integer.MIN_VALUE, Integer.MAX_VALUE);
    }

    public static boolean verify(int[] sequence, int start, int end, int max, int min) {
        int root = sequence[end];
        int middle = 0;
        middle = end;
        if (start >= end) {
            return true;
        }
        for (int i = start; i <= end; i++) {
            if (sequence[i] < sequence[middle] && sequence[i + 1] > sequence[middle]) {
                middle = i;
                break;
            }

        }
        if (middle == end) {
            return true;
        }
        if (verify(sequence, start, middle, max, min) &&
                verify(sequence, middle + 1, end - 1, max, min)) {
            if (start <= middle) {
                max = Math.max(max, getMax(start, middle, sequence));
            }
            if (end - 1 >= middle + 1) {
                min = Math.min(min, getMin(middle + 1, end - 1, sequence));
            }

            if (root < max || root > min) {
                return false;
            }
        }

        return true;
    }

    private static int getMin(int middle, int end, int[] sequence) {
        int min = sequence[middle];
        for (int i = middle + 1; i <= end; i++) {
            if (sequence[i] < min) {
                min = sequence[i];
            }
        }
        return min;
    }

    public static int getMax(int start, int middle, int[] sequence) {
        int max = sequence[start];
        for (int i = start + 1; i <= middle; i++) {
            if (sequence[i] > max) {
                max = sequence[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
//        int[] arr = {2, 4, 3, 6, 9, 8, 5};
        int[] arr = {1,2,7,4,5};
//        int[] arr = {7,4,6,5};
        System.out.println(VerifySquenceOfBST(arr));
    }
}
